/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：BucketSort.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-29
Function List ：
Description   ：Bucket Sort
******************************************************/

#include "BucketSort.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"

#define MaxBucketNum    30
#define MaxElementValue 999

typedef struct Node *PtrToNode;
typedef PtrToNode *Bucket;

struct Node {
    ElementType Element;
    PtrToNode   Next;
};

// Static Function Lists
static Bucket InitializeBucket();
static void DestroyBucket(Bucket B);
__attribute__((unused)) static void PrintBucket(Bucket B);  // for warning

static Bucket InitializeBucket() {
    Bucket B;
    int i;

    B = (Bucket)malloc(MaxBucketNum * sizeof(PtrToNode));
    if (B == NULL) {
        FatalError("Out of space!!!");
    }

    for (i = 0; i < MaxBucketNum; ++i) {
        B[i] = (PtrToNode)malloc(sizeof(struct Node));
        if (B[i] == NULL) {
            FatalError("Out of space!!!");
        } else {
            B[i]->Next = NULL;
        }
    }

    return B;
}

static void DestroyBucket(Bucket B) {
    int i;
    PtrToNode Pre;
    PtrToNode Cur;

    for (i = 0; i < MaxBucketNum; ++i) {
        Cur = B[i];
        while (Cur != NULL) {
            Pre = Cur;
            Cur = Cur->Next;
            free(Pre);
        }
    }

    free(B);
}

static void PrintBucket(Bucket B) {
    int i;
    PtrToNode Tmp;

    if (B != NULL) {
        for (i = 0; i < MaxBucketNum; ++i) {
            Tmp = B[i];
            printf("%02d | ", i);
            while (Tmp->Next != NULL) {
                printf("-> %d ", Tmp->Next->Element);
                Tmp = Tmp->Next;
            }
            printf("-> ^\n");
        }
    }
}

void BucketSort(ElementType A[], int N) {
    int i;
    int j;
    int index;
    Bucket B;
    PtrToNode Tmp;
    PtrToNode NewCell;

    /* Initialize bucket */
    B = InitializeBucket();

    /* Put array elements in the ordered list */
    for (i = 0; i < N; ++i) {
        index = (A[i] * MaxBucketNum) / (MaxElementValue + 1);
        Tmp = B[index];
        while (Tmp != NULL) {
            if (Tmp->Next != NULL && A[i] > Tmp->Next->Element) {
                Tmp = Tmp->Next;
            } else {
                /* Find finished */
                NewCell = (PtrToNode)malloc(sizeof(struct Node));
                if (NewCell == NULL) {
                    FatalError("Out of space!!!");
                }

                NewCell->Element = A[i];
                NewCell->Next = Tmp->Next;
                Tmp->Next = NewCell;
                break;
            }
        }
    }

    // PrintBucket(B);

    /* Put ordered list elements in array */
    j = 0;
    for (i = 0; i < MaxBucketNum; ++i) {
        Tmp = B[i];
        while (Tmp->Next != NULL) {
            A[j++] = Tmp->Next->Element;
            Tmp = Tmp->Next;
        }
    }

    /* Destroy bucket */
    DestroyBucket(B);
}

// EOF

